home *** CD-ROM | disk | FTP | other *** search
/ The Very Best of Atari Inside / The Very Best of Atari Inside 1.iso / mint / mntlb20 / lib / regexp.c < prev    next >
C/C++ Source or Header  |  1990-09-24  |  29KB  |  1,084 lines
  1. /* MODIFIED VERSION -- see below */
  2.  
  3. /* regcomp and regexec -- regsub and regerror are elsewhere
  4.  *
  5.  *    Copyright (c) 1986 by University of Toronto.
  6.  *    Written by Henry Spencer.  Not derived from licensed software.
  7.  *
  8.  *    Permission is granted to anyone to use this software for any
  9.  *    purpose on any computer system, and to redistribute it freely,
  10.  *    subject to the following restrictions:
  11.  *
  12.  *    1. The author is not responsible for the consequences of use of
  13.  *        this software, no matter how awful, even if they arise
  14.  *        from defects in it.
  15.  *
  16.  *    2. The origin of this software must not be misrepresented, either
  17.  *        by explicit claim or by omission.
  18.  *
  19.  *    3. Altered versions must be plainly marked as such, and must not
  20.  *        be misrepresented as being the original software.
  21.  *
  22.  * Beware that some of this code is subtly aware of the way operator
  23.  * precedence is structured in regular expressions.  Serious changes in
  24.  * regular-expression syntax might require a total rethink.
  25.  *
  26.  *    The third parameter to regexec was added by Martin C. Atkins.
  27.  *    Andy Tanenbaum also made some changes.
  28.  *      Eric Smith modified it a bit to compile with the MiNT library
  29.  */
  30.  
  31. #include <stdlib.h>
  32. #include <string.h>
  33. #include <regexp.h>
  34. #include <stdio.h>
  35.  
  36. /* The first byte of the regexp internal "program" is actually this magic
  37.  * number; the start node begins in the second byte.
  38.  */
  39. #define    MAGIC    0234
  40.  
  41. /* The "internal use only" fields in regexp.h are present to pass info from
  42.  * compile to execute that permits the execute phase to run lots faster on
  43.  * simple cases.  They are:
  44.  *
  45.  * regstart    char that must begin a match; '\0' if none obvious
  46.  * reganch    is the match anchored (at beginning-of-line only)?
  47.  * regmust    string (pointer into program) that match must include, or NULL
  48.  * regmlen    length of regmust string
  49.  *
  50.  * Regstart and reganch permit very fast decisions on suitable starting points
  51.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  52.  * of lines that cannot possibly match.  The regmust tests are costly enough
  53.  * that regcomp() supplies a regmust only if the r.e. contains something
  54.  * potentially expensive (at present, the only such thing detected is * or +
  55.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  56.  * supplied because the test in regexec() needs it and regcomp() is computing
  57.  * it anyway.
  58.  */
  59.  
  60. /* Structure for regexp "program".  This is essentially a linear encoding
  61.  * of a nondeterministic finite-state machine (aka syntax charts or
  62.  * "railroad normal form" in parsing technology).  Each node is an opcode
  63.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  64.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  65.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  66.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  67.  * opposed to a collection of them) is never concatenated with anything
  68.  * because of operator precedence.)  The operand of some types of node is
  69.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  70.  * particular, the operand of a BRANCH node is the first node of the branch.
  71.  * (NB this is *not* a tree structure:  the tail of the branch connects
  72.  * to the thing following the set of BRANCHes.)  The opcodes are:
  73.  */
  74.  
  75. /* Definition    number    opnd?    meaning */
  76. #define    END    0        /* no    End of program. */
  77. #define    BOL    1        /* no    Match "" at beginning of line. */
  78. #define    EOL    2        /* no    Match "" at end of line. */
  79. #define    ANY    3        /* no    Match any one character. */
  80. #define    ANYOF    4        /* str    Match any character in this string. */
  81. #define    ANYBUT    5        /* str    Match any character not in this
  82.              * string. */
  83. #define    BRANCH    6        /* node    Match this alternative, or the
  84.              * next... */
  85. #define    BACK    7        /* no    Match "", "next" ptr points backward. */
  86. #define    EXACTLY    8        /* str    Match this string. */
  87. #define    NOTHING    9        /* no    Match empty string. */
  88. #define    STAR    10        /* node    Match this (simple) thing 0 or more
  89.              * times. */
  90. #define    PLUS    11        /* node    Match this (simple) thing 1 or more
  91.              * times. */
  92. #define    OPEN    20        /* no    Mark this point in input as start of
  93.              * #n. */
  94.  /* OPEN+1 is number 1, etc. */
  95. #define    CLOSE    30        /* no    Analogous to OPEN. */
  96.  
  97. /* Opcode notes:
  98.  *
  99.  * BRANCH    The set of branches constituting a single choice are hooked
  100.  *        together with their "next" pointers, since precedence prevents
  101.  *        anything being concatenated to any individual branch.  The
  102.  *        "next" pointer of the last BRANCH in a choice points to the
  103.  *        thing following the whole choice.  This is also where the
  104.  *        final "next" pointer of each individual branch points; each
  105.  *        branch starts with the operand node of a BRANCH node.
  106.  *
  107.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  108.  *        exists to make loop structures possible.
  109.  *
  110.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  111.  *        BRANCH structures using BACK.  Simple cases (one character
  112.  *        per match) are implemented with STAR and PLUS for speed
  113.  *        and to minimize recursive plunges.
  114.  *
  115.  * OPEN,CLOSE    ...are numbered at compile time.
  116.  */
  117.  
  118. /* A node is one char of opcode followed by two chars of "next" pointer.
  119.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  120.  * value is a positive offset from the opcode of the node containing it.
  121.  * An operand, if any, simply follows the node.  (Note that much of the
  122.  * code generation knows about this implicit relationship.)
  123.  *
  124.  * Using two bytes for the "next" pointer is vast overkill for most things,
  125.  * but allows patterns to get big without disasters.
  126.  */
  127. #define    OP(p)    (*(p))
  128. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  129. #define    OPERAND(p)    ((p) + 3)
  130.  
  131. /* Utility definitions.
  132.  */
  133. #ifndef CHARBITS
  134. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  135. #else
  136. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  137. #endif
  138.  
  139. #define    CFAIL(m)    { regerror(m); return((char *)NULL); }
  140. #define    RFAIL(m)    { regerror(m); return((regexp *)NULL); }
  141. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  142. #define    META    "^$.[()|?+*\\"
  143.  
  144. /* Flags to be passed up and down.
  145.  */
  146. #define    HASWIDTH    01    /* Known never to match null string. */
  147. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  148. #define    SPSTART        04    /* Starts with * or +. */
  149. #define    WORST        0    /* Worst case. */
  150.  
  151. /* Global work variables for regcomp().
  152.  */
  153. static char *regparse;        /* Input-scan pointer. */
  154. static int regnpar;        /* () count. */
  155. static char regdummy;
  156. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  157. static long regsize;        /* Code size. */
  158.  
  159. /* Forward declarations for regcomp()'s friends.
  160.  */
  161. #ifndef STATIC
  162. #define    STATIC    static
  163. #endif
  164. #ifndef _PROTOTYPE
  165. # if __STDC__
  166. #  define _PROTOTYPE(a, b) a b
  167. # else
  168. #  define _PROTOTYPE(a,b) a ()
  169. # endif
  170. #endif
  171.  
  172. STATIC _PROTOTYPE( char *reg, (int paren, int *flagp)            );
  173. STATIC _PROTOTYPE( char *regbranch, (int *flagp)            );
  174. STATIC _PROTOTYPE( char *regpiece, (int *flagp)                );
  175. STATIC _PROTOTYPE( char *regatom, (int *flagp)                );
  176. STATIC _PROTOTYPE( char *regnode, (int op)                );
  177. STATIC _PROTOTYPE( char *regnext, (char *p)                );
  178. STATIC _PROTOTYPE( void regc, (int b)                    );
  179. STATIC _PROTOTYPE( void reginsert, (int op, char *opnd)            );
  180. STATIC _PROTOTYPE( void regtail, (char *p, char *val)            );
  181. STATIC _PROTOTYPE( void regoptail, (char *p, char *val)            );
  182.  
  183. /*
  184.  - regcomp - compile a regular expression into internal code
  185.  *
  186.  * We can't allocate space until we know how big the compiled form will be,
  187.  * but we can't compile it (and thus know how big it is) until we've got a
  188.  * place to put the code.  So we cheat:  we compile it twice, once with code
  189.  * generation turned off and size counting turned on, and once "for real".
  190.  * This also means that we don't allocate space until we are sure that the
  191.  * thing really will compile successfully, and we never have to move the
  192.  * code and thus invalidate pointers into it.  (Note that it has to be in
  193.  * one piece because free() must be able to free it all.)
  194.  *
  195.  * Beware that the optimization-preparation code in here knows about some
  196.  * of the structure of the compiled regexp.
  197.  */
  198. regexp *regcomp(exp)
  199. char *exp;
  200. {
  201.   register regexp *r;
  202.   register char *scan;
  203.   register char *longest;
  204.   register int len;
  205.   int flags;
  206.  
  207.   if (exp == (char *)NULL) RFAIL("NULL argument");
  208.  
  209.   /* First pass: determine size, legality. */
  210.   regparse = exp;
  211.   regnpar = 1;
  212.   regsize = 0L;
  213.   regcode = ®dummy;
  214.   regc(MAGIC);
  215.   if (reg(0, &flags) == (char *)NULL) return((regexp *)NULL);
  216.  
  217.   /* Small enough for pointer-storage convention? */
  218.   if (regsize >= 32767L)    /* Probably could be 65535L. */
  219.     RFAIL("regexp too big");
  220.  
  221.   /* Allocate space. */
  222.   r = (regexp *) malloc(sizeof(regexp) + (unsigned) regsize);
  223.   if (r == (regexp *)NULL) RFAIL("out of space");
  224.  
  225.   /* Second pass: emit code. */
  226.   regparse = exp;
  227.   regnpar = 1;
  228.   regcode = r->program;
  229.   regc(MAGIC);
  230.   if (reg(0, &flags) == (char *)NULL) return((regexp *)NULL);
  231.  
  232.   /* Dig out information for optimizations. */
  233.   r->regstart = '\0';        /* Worst-case defaults. */
  234.   r->reganch = 0;
  235.   r->regmust = (char *)NULL;
  236.   r->regmlen = 0;
  237.   scan = r->program + 1;    /* First BRANCH. */
  238.   if (OP(regnext(scan)) == END) {    /* Only one top-level choice. */
  239.     scan = OPERAND(scan);
  240.  
  241.     /* Starting-point info. */
  242.     if (OP(scan) == EXACTLY)
  243.         r->regstart = *OPERAND(scan);
  244.     else if (OP(scan) == BOL)
  245.         r->reganch++;
  246.  
  247.     /* If there's something expensive in the r.e., find the
  248.      * longest literal string that must appear and make it the
  249.      * regmust.  Resolve ties in favor of later strings, since
  250.      * the regstart check works with the beginning of the r.e.
  251.      * and avoiding duplication strengthens checking.  Not a
  252.      * strong reason, but sufficient in the absence of others. */
  253.     if (flags & SPSTART) {
  254.         longest = (char *)NULL;
  255.         len = 0;
  256.         for (; scan != (char *)NULL; scan = regnext(scan))
  257.             if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  258.                 longest = OPERAND(scan);
  259.                 len = strlen(OPERAND(scan));
  260.             }
  261.         r->regmust = longest;
  262.         r->regmlen = len;
  263.     }
  264.   }
  265.   return(r);
  266. }
  267.  
  268. /*
  269.  - reg - regular expression, i.e. main body or parenthesized thing
  270.  *
  271.  * Caller must absorb opening parenthesis.
  272.  *
  273.  * Combining parenthesis handling with the base level of regular expression
  274.  * is a trifle forced, but the need to tie the tails of the branches to what
  275.  * follows makes it hard to avoid.
  276.  */
  277. static char *reg(paren, flagp)
  278. int paren;            /* Parenthesized? */
  279. int *flagp;
  280. {
  281.   register char *ret;
  282.   register char *br;
  283.   register char *ender;
  284.   register int parno;
  285.   int flags;
  286.  
  287.   *flagp = HASWIDTH;        /* Tentatively. */
  288.  
  289.   /* Make an OPEN node, if parenthesized. */
  290.   if (paren) {
  291.     if (regnpar >= NSUBEXP) CFAIL("too many ()");
  292.     parno = regnpar;
  293.     regnpar++;
  294.     ret = regnode(OPEN + parno);
  295.   } else {
  296.     parno = 0;        /* not actually used, keep compiler quiet */
  297.     ret = (char *)NULL;
  298.   }
  299.  
  300.   /* Pick up the branches, linking them together. */
  301.   br = regbranch(&flags);
  302.   if (br == (char *)NULL) return((char *)NULL);
  303.   if (ret != (char *)NULL)
  304.     regtail(ret, br);    /* OPEN -> first. */
  305.   else
  306.     ret = br;
  307.   if (!(flags & HASWIDTH)) *flagp &= ~HASWIDTH;
  308.   *flagp |= flags & SPSTART;
  309.   while (*regparse == '|') {
  310.     regparse++;
  311.     br = regbranch(&flags);
  312.     if (br == (char *)NULL) return((char *)NULL);
  313.     regtail(ret, br);    /* BRANCH -> BRANCH. */
  314.     if (!(flags & HASWIDTH)) *flagp &= ~HASWIDTH;
  315.     *flagp |= flags & SPSTART;
  316.   }
  317.  
  318.   /* Make a closing node, and hook it on the end. */
  319.   ender = regnode((paren) ? CLOSE + parno : END);
  320.   regtail(ret, ender);
  321.  
  322.   /* Hook the tails of the branches to the closing node. */
  323.   for (br = ret; br != (char *)NULL; br = regnext(br)) regoptail(br, ender);
  324.  
  325.   /* Check for proper termination. */
  326.   if (paren && *regparse++ != ')') {
  327.     CFAIL("unmatched ()");
  328.   } else if (!paren && *regparse != '\0') {
  329.     if (*regparse == ')') {
  330.         CFAIL("unmatched ()");
  331.     } else
  332.         CFAIL("junk on end");    /* "Can't happen". */
  333.     /* NOTREACHED */
  334.   }
  335.   return(ret);
  336. }
  337.  
  338. /*
  339.  - regbranch - one alternative of an | operator
  340.  *
  341.  * Implements the concatenation operator.
  342.  */
  343. static char *regbranch(flagp)
  344. int *flagp;
  345. {
  346.   register char *ret;
  347.   register char *chain;
  348.   register char *latest;
  349.   int flags;
  350.  
  351.   *flagp = WORST;        /* Tentatively. */
  352.  
  353.   ret = regnode(BRANCH);
  354.   chain = (char *)NULL;
  355.   while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  356.     latest = regpiece(&flags);
  357.     if (latest == (char *)NULL) return((char *)NULL);
  358.     *flagp |= flags & HASWIDTH;
  359.     if (chain == (char *)NULL)    /* First piece. */
  360.         *flagp |= flags & SPSTART;
  361.     else
  362.         regtail(chain, latest);
  363.     chain = latest;
  364.   }
  365.   if (chain == (char *)NULL)        /* Loop ran zero times. */
  366.     regnode(NOTHING);
  367.  
  368.   return(ret);
  369. }
  370.  
  371. /*
  372.  - regpiece - something followed by possible [*+?]
  373.  *
  374.  * Note that the branching code sequences used for ? and the general cases
  375.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  376.  * both the endmarker for their branch list and the body of the last branch.
  377.  * It might seem that this node could be dispensed with entirely, but the
  378.  * endmarker role is not redundant.
  379.  */
  380. static char *regpiece(flagp)
  381. int *flagp;
  382. {
  383.   register char *ret;
  384.   register char op;
  385.   register char *next;
  386.   int flags;
  387.  
  388.   ret = regatom(&flags);
  389.   if (ret == (char *)NULL) return((char *)NULL);
  390.  
  391.   op = *regparse;
  392.   if (!ISMULT(op)) {
  393.     *flagp = flags;
  394.     return(ret);
  395.   }
  396.   if (!(flags & HASWIDTH) && op != '?') CFAIL("*+ operand could be empty");
  397.   *flagp = (op != '+') ? (WORST | SPSTART) : (WORST | HASWIDTH);
  398.  
  399.   if (op == '*' && (flags & SIMPLE))
  400.     reginsert(STAR, ret);
  401.   else if (op == '*') {
  402.     /* Emit x* as (x&|), where & means "self". */
  403.     reginsert(BRANCH, ret);    /* Either x */
  404.     regoptail(ret, regnode(BACK));    /* and loop */
  405.     regoptail(ret, ret);    /* back */
  406.     regtail(ret, regnode(BRANCH));    /* or */
  407.     regtail(ret, regnode(NOTHING));    /* null. */
  408.   } else if (op == '+' && (flags & SIMPLE))
  409.     reginsert(PLUS, ret);
  410.   else if (op == '+') {
  411.     /* Emit x+ as x(&|), where & means "self". */
  412.     next = regnode(BRANCH);    /* Either */
  413.     regtail(ret, next);
  414.     regtail(regnode(BACK), ret);    /* loop back */
  415.     regtail(next, regnode(BRANCH));    /* or */
  416.     regtail(ret, regnode(NOTHING));    /* null. */
  417.   } else if (op == '?') {
  418.     /* Emit x? as (x|) */
  419.     reginsert(BRANCH, ret);    /* Either x */
  420.     regtail(ret, regnode(BRANCH));    /* or */
  421.     next = regnode(NOTHING);/* null. */
  422.     regtail(ret, next);
  423.     regoptail(ret, next);
  424.   }
  425.   regparse++;
  426.   if (ISMULT(*regparse)) CFAIL("nested *?+");
  427.  
  428.   return(ret);
  429. }
  430.  
  431. /*
  432.  - regatom - the lowest level
  433.  *
  434.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  435.  * it can turn them into a single node, which is smaller to store and
  436.  * faster to run.  Backslashed characters are exceptions, each becoming a
  437.  * separate node; the code is simpler that way and it's not worth fixing.
  438.  */
  439. static char *regatom(flagp)
  440. int *flagp;
  441. {
  442.   register char *ret;
  443.   int flags;
  444.  
  445.   *flagp = WORST;        /* Tentatively. */
  446.  
  447.   switch (*regparse++) {
  448.       case '^':    ret = regnode(BOL);          break;
  449.       case '$':    ret = regnode(EOL);          break;
  450.       case '.':
  451.     ret = regnode(ANY);
  452.     *flagp |= HASWIDTH | SIMPLE;
  453.     break;
  454.       case '[':{
  455.         register int class;
  456.         register int classend;
  457.  
  458.         if (*regparse == '^') {    /* Complement of range. */
  459.             ret = regnode(ANYBUT);
  460.             regparse++;
  461.         } else
  462.             ret = regnode(ANYOF);
  463.         if (*regparse == ']' || *regparse == '-') regc(*regparse++);
  464.         while (*regparse != '\0' && *regparse != ']') {
  465.             if (*regparse == '-') {
  466.                 regparse++;
  467.                 if (*regparse == ']' || *regparse == '\0')
  468.                     regc('-');
  469.                 else {
  470.                     class = UCHARAT(regparse - 2) + 1;
  471.                     classend = UCHARAT(regparse);
  472.                     if (class > classend + 1)
  473.                         CFAIL("invalid [] range");
  474.                     for (; class <= classend; class++)
  475.                         regc(class);
  476.                     regparse++;
  477.                 }
  478.             } else
  479.                 regc(*regparse++);
  480.         }
  481.         regc('\0');
  482.         if (*regparse != ']') CFAIL("unmatched []");
  483.         regparse++;
  484.         *flagp |= HASWIDTH | SIMPLE;
  485.     }
  486.     break;
  487.       case '(':
  488.     ret = reg(1, &flags);
  489.     if (ret == (char *)NULL) return((char *)NULL);
  490.     *flagp |= flags & (HASWIDTH | SPSTART);
  491.     break;
  492.       case '\0':
  493.       case '|':
  494.       case ')':
  495.     CFAIL("internal urp");    /* Supposed to be caught earlier. */
  496.     break;
  497.       case '?':
  498.       case '+':
  499.       case '*':    CFAIL("?+* follows nothing");          break;
  500.       case '\\':
  501.     if (*regparse == '\0') CFAIL("trailing \\");
  502.     ret = regnode(EXACTLY);
  503.     regc(*regparse++);
  504.     regc('\0');
  505.     *flagp |= HASWIDTH | SIMPLE;
  506.     break;
  507.       default:{
  508.         register int len;
  509.         register char ender;
  510.  
  511.         regparse--;
  512.         len = strcspn(regparse, META);
  513.         if (len <= 0) CFAIL("internal disaster");
  514.         ender = *(regparse + len);
  515.         if (len > 1 && ISMULT(ender))
  516.             len--;    /* Back off clear of ?+* operand. */
  517.         *flagp |= HASWIDTH;
  518.         if (len == 1) *flagp |= SIMPLE;
  519.         ret = regnode(EXACTLY);
  520.         while (len > 0) {
  521.             regc(*regparse++);
  522.             len--;
  523.         }
  524.         regc('\0');
  525.     }
  526.     break;
  527.   }
  528.  
  529.   return(ret);
  530. }
  531.  
  532. /*
  533.  - regnode - emit a node
  534.  */
  535. static char *regnode(op)
  536. char op;
  537. {
  538.   register char *ret;
  539.   register char *ptr;
  540.  
  541.   ret = regcode;
  542.   if (ret == ®dummy) {
  543.     regsize += 3;
  544.     return(ret);
  545.   }
  546.   ptr = ret;
  547.   *ptr++ = op;
  548.   *ptr++ = '\0';        /* Null "next" pointer. */
  549.   *ptr++ = '\0';
  550.   regcode = ptr;
  551.  
  552.   return(ret);
  553. }
  554.  
  555. /*
  556.  - regc - emit (if appropriate) a byte of code
  557.  */
  558. static void regc(b)
  559. char b;
  560. {
  561.   if (regcode != ®dummy)
  562.     *regcode++ = b;
  563.   else
  564.     regsize++;
  565. }
  566.  
  567. /*
  568.  - reginsert - insert an operator in front of already-emitted operand
  569.  *
  570.  * Means relocating the operand.
  571.  */
  572. static void reginsert(op, opnd)
  573. char op;
  574. char *opnd;
  575. {
  576.   register char *src;
  577.   register char *dst;
  578.   register char *place;
  579.  
  580.   if (regcode == ®dummy) {
  581.     regsize += 3;
  582.     return;
  583.   }
  584.   src = regcode;
  585.   regcode += 3;
  586.   dst = regcode;
  587.   while (src > opnd) *--dst = *--src;
  588.  
  589.   place = opnd;            /* Op node, where operand used to be. */
  590.   *place++ = op;
  591.   *place++ = '\0';
  592.   *place++ = '\0';
  593. }
  594.  
  595. /*
  596.  - regtail - set the next-pointer at the end of a node chain
  597.  */
  598. static void regtail(p, val)
  599. char *p;
  600. char *val;
  601. {
  602.   register char *scan;
  603.   register char *temp;
  604.   register int offset;
  605.  
  606.   if (p == ®dummy) return;
  607.  
  608.   /* Find last node. */
  609.   scan = p;
  610.   for (;;) {
  611.     temp = regnext(scan);
  612.     if (temp == (char *)NULL) break;
  613.     scan = temp;
  614.   }
  615.  
  616.   if (OP(scan) == BACK)
  617.     offset = scan - val;
  618.   else
  619.     offset = val - scan;
  620.   *(scan + 1) = (offset >> 8) & 0377;
  621.   *(scan + 2) = offset & 0377;
  622. }
  623.  
  624. /*
  625.  - regoptail - regtail on operand of first argument; nop if operandless
  626.  */
  627. static void regoptail(p, val)
  628. char *p;
  629. char *val;
  630. {
  631.   /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  632.   if (p == (char *)NULL || p == ®dummy || OP(p) != BRANCH) return;
  633.   regtail(OPERAND(p), val);
  634. }
  635.  
  636. /* regexec and friends
  637.  */
  638.  
  639. /* Global work variables for regexec().
  640.  */
  641. static char *reginput;        /* String-input pointer. */
  642. static char *regbol;        /* Beginning of input, for ^ check. */
  643. static char **regstartp;    /* Pointer to startp array. */
  644. static char **regendp;        /* Ditto for endp. */
  645.  
  646. /* Forwards.
  647.  */
  648. STATIC _PROTOTYPE( int regtry, (regexp *prog, char *string)        );
  649. STATIC _PROTOTYPE( int regmatch, (char *prog)                );
  650. STATIC _PROTOTYPE( int regrepeat, (char *p)                );
  651.  
  652. #ifdef DEBUG
  653. int regnarrate = 0;
  654. void regdump();
  655. STATIC _PROTOTYPE( char *regprop, (char *op)                );
  656. #endif
  657.  
  658. /*
  659.  - regexec - match a regexp against a string
  660.  */
  661. int regexec(prog, string, bolflag)
  662. register regexp *prog;
  663. register char *string;
  664. int bolflag;
  665. {
  666.   register char *s;
  667.  
  668.   /* Be paranoid... */
  669.   if (prog == (regexp *)NULL || string == (char *)NULL) {
  670.     regerror("NULL parameter");
  671.     return(0);
  672.   }
  673.  
  674.   /* Check validity of program. */
  675.   if (UCHARAT(prog->program) != MAGIC) {
  676.     regerror("corrupted program");
  677.     return(0);
  678.   }
  679.  
  680.   /* If there is a "must appear" string, look for it. */
  681.   if (prog->regmust != (char *)NULL) {
  682.     s = string;
  683.     while ((s = strchr(s, prog->regmust[0])) != (char *)NULL) {
  684.         if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  685.             break;    /* Found it. */
  686.         s++;
  687.     }
  688.     if (s == (char *)NULL)        /* Not present. */
  689.         return(0);
  690.   }
  691.  
  692.   /* Mark beginning of line for ^ . */
  693.   if (bolflag)
  694.     regbol = string;
  695.   else
  696.     regbol = (char *)NULL;
  697.  
  698.   /* Simplest case:  anchored match need be tried only once. */
  699.   if (prog->reganch) return(regtry(prog, string));
  700.  
  701.   /* Messy cases:  unanchored match. */
  702.   s = string;
  703.   if (prog->regstart != '\0')     /* We know what char it must start with. */
  704.     while ((s = strchr(s, prog->regstart)) != (char *)NULL) {
  705.         if (regtry(prog, s)) return(1);
  706.         s++;
  707.     }
  708.   else
  709.     /* We don't -- general case. */
  710.     do {
  711.         if (regtry(prog, s)) return(1);
  712.     } while (*s++ != '\0');
  713.  
  714.   /* Failure. */
  715.   return(0);
  716. }
  717.  
  718. /*
  719.  - regtry - try match at specific point
  720.  */
  721. static int regtry(prog, string)   /* 0 failure, 1 success */
  722. regexp *prog;
  723. char *string;
  724. {
  725.   register int i;
  726.   register char **sp;
  727.   register char **ep;
  728.  
  729.   reginput = string;
  730.   regstartp = prog->startp;
  731.   regendp = prog->endp;
  732.  
  733.   sp = prog->startp;
  734.   ep = prog->endp;
  735.   for (i = NSUBEXP; i > 0; i--) {
  736.     *sp++ = (char *)NULL;
  737.     *ep++ = (char *)NULL;
  738.   }
  739.   if (regmatch(prog->program + 1)) {
  740.     prog->startp[0] = string;
  741.     prog->endp[0] = reginput;
  742.     return(1);
  743.   } else
  744.     return(0);
  745. }
  746.  
  747. /*
  748.  - regmatch - main matching routine
  749.  *
  750.  * Conceptually the strategy is simple:  check to see whether the current
  751.  * node matches, call self recursively to see whether the rest matches,
  752.  * and then act accordingly.  In practice we make some effort to avoid
  753.  * recursion, in particular by going through "ordinary" nodes (that don't
  754.  * need to know whether the rest of the match failed) by a loop instead of
  755.  * by recursion.
  756.  */
  757. static int regmatch(prog)    /* 0 failure, 1 success */ 
  758. char *prog;
  759. {
  760.   register char *scan;        /* Current node. */
  761.   char *next;            /* Next node. */
  762.  
  763.   scan = prog;
  764. #ifdef DEBUG
  765.   if (scan != (char *)NULL && regnarrate) fprintf(stderr, "%s(\n", regprop(scan));
  766. #endif
  767.   while (scan != (char *)NULL) {
  768. #ifdef DEBUG
  769.     if (regnarrate) fprintf(stderr, "%s...\n", regprop(scan));
  770. #endif
  771.     next = regnext(scan);
  772.  
  773.     switch (OP(scan)) {
  774.         case BOL:
  775.         if (reginput != regbol) return(0);
  776.         break;
  777.         case EOL:
  778.         if (*reginput != '\0') return(0);
  779.         break;
  780.         case ANY:
  781.         if (*reginput == '\0') return(0);
  782.         reginput++;
  783.         break;
  784.         case EXACTLY:{
  785.             register int len;
  786.             register char *opnd;
  787.  
  788.             opnd = OPERAND(scan);
  789.             /* Inline the first character, for speed. */
  790.             if (*opnd != *reginput) return(0);
  791.             len = strlen(opnd);
  792.             if (len > 1 && strncmp(opnd, reginput, len) != 0)
  793.                 return(0);
  794.             reginput += len;
  795.         }
  796.         break;
  797.         case ANYOF:
  798.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == (char *)NULL)
  799.             return(0);
  800.         reginput++;
  801.         break;
  802.         case ANYBUT:
  803.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != (char *)NULL)
  804.             return(0);
  805.         reginput++;
  806.         break;
  807.         case NOTHING:
  808.         break;
  809.         case BACK:
  810.         break;
  811.         case OPEN + 1:
  812.         case OPEN + 2:
  813.         case OPEN + 3:
  814.         case OPEN + 4:
  815.         case OPEN + 5:
  816.         case OPEN + 6:
  817.         case OPEN + 7:
  818.         case OPEN + 8:
  819.         case OPEN + 9:{
  820.             register int no;
  821.             register char *save;
  822.  
  823.             no = OP(scan) - OPEN;
  824.             save = reginput;
  825.  
  826.             if (regmatch(next)) {
  827.                 /* Don't set startp if some later
  828.                  * invocation of the same parentheses
  829.                  * already has. */
  830.                 if (regstartp[no] == (char *)NULL)
  831.                     regstartp[no] = save;
  832.                 return(1);
  833.             } else
  834.                 return(0);
  835.         }
  836.         break;
  837.         case CLOSE + 1:
  838.         case CLOSE + 2:
  839.         case CLOSE + 3:
  840.         case CLOSE + 4:
  841.         case CLOSE + 5:
  842.         case CLOSE + 6:
  843.         case CLOSE + 7:
  844.         case CLOSE + 8:
  845.         case CLOSE + 9:{
  846.             register int no;
  847.             register char *save;
  848.  
  849.             no = OP(scan) - CLOSE;
  850.             save = reginput;
  851.  
  852.             if (regmatch(next)) {
  853.                 /* Don't set endp if some later
  854.                  * invocation of the same parentheses
  855.                  * already has. */
  856.                 if (regendp[no] == (char *)NULL) regendp[no] = save;
  857.                 return(1);
  858.             } else
  859.                 return(0);
  860.         }
  861.         break;
  862.         case BRANCH:{
  863.             register char *save;
  864.  
  865.             if (OP(next) != BRANCH)    /* No choice. */
  866.                 next = OPERAND(scan);    /* Avoid recursion. */
  867.             else {
  868.                 do {
  869.                     save = reginput;
  870.                     if (regmatch(OPERAND(scan)))
  871.                         return(1);
  872.                     reginput = save;
  873.                     scan = regnext(scan);
  874.                 } while (scan != (char *)NULL && OP(scan) == BRANCH);
  875.                 return(0);
  876.                 /* NOTREACHED */
  877.             }
  878.         }
  879.         break;
  880.         case STAR:
  881.         case PLUS:{
  882.             register char nextch;
  883.             register int no;
  884.             register char *save;
  885.             register int min;
  886.  
  887.             /* Lookahead to avoid useless match attempts
  888.              * when we know what character comes next. */
  889.             nextch = '\0';
  890.             if (OP(next) == EXACTLY) nextch = *OPERAND(next);
  891.             min = (OP(scan) == STAR) ? 0 : 1;
  892.             save = reginput;
  893.             no = regrepeat(OPERAND(scan));
  894.             while (no >= min) {
  895.                 /* If it could work, try it. */
  896.                 if (nextch == '\0' || *reginput == nextch)
  897.                     if (regmatch(next)) return(1);
  898.                 /* Couldn't or didn't -- back up. */
  899.                 no--;
  900.                 reginput = save + no;
  901.             }
  902.             return(0);
  903.         }
  904.         break;
  905.         case END:
  906.         return(1);    /* Success! */
  907.         break;
  908.         default:
  909.         regerror("memory corruption");
  910.         return(0);
  911.         break;
  912.     }
  913.  
  914.     scan = next;
  915.   }
  916.  
  917.   /* We get here only if there's trouble -- normally "case END" is the
  918.    * terminating point. */
  919.   regerror("corrupted pointers");
  920.   return(0);
  921. }
  922.  
  923. /*
  924.  - regrepeat - repeatedly match something simple, report how many
  925.  */
  926. static int regrepeat(p)
  927. char *p;
  928. {
  929.   register int count = 0;
  930.   register char *scan;
  931.   register char *opnd;
  932.  
  933.   scan = reginput;
  934.   opnd = OPERAND(p);
  935.   switch (OP(p)) {
  936.       case ANY:
  937.     count = strlen(scan);
  938.     scan += count;
  939.     break;
  940.       case EXACTLY:
  941.     while (*opnd == *scan) {
  942.         count++;
  943.         scan++;
  944.     }
  945.     break;
  946.       case ANYOF:
  947.     while (*scan != '\0' && strchr(opnd, *scan) != (char *)NULL) {
  948.         count++;
  949.         scan++;
  950.     }
  951.     break;
  952.       case ANYBUT:
  953.     while (*scan != '\0' && strchr(opnd, *scan) == (char *)NULL) {
  954.         count++;
  955.         scan++;
  956.     }
  957.     break;
  958.       default:            /* Oh dear.  Called inappropriately. */
  959.     regerror("internal foulup");
  960.     count = 0;        /* Best compromise. */
  961.     break;
  962.   }
  963.   reginput = scan;
  964.  
  965.   return(count);
  966. }
  967.  
  968. /*
  969.  - regnext - dig the "next" pointer out of a node
  970.  */
  971. static char *regnext(p)
  972. register char *p;
  973. {
  974.   register int offset;
  975.  
  976.   if (p == ®dummy) return((char *)NULL);
  977.  
  978.   offset = NEXT(p);
  979.   if (offset == 0) return((char *)NULL);
  980.  
  981.   if (OP(p) == BACK)
  982.     return(p - offset);
  983.   else
  984.     return(p + offset);
  985. }
  986.  
  987. #ifdef DEBUG
  988.  
  989. STATIC char *regprop();
  990.  
  991. /*
  992.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  993.  */
  994. void regdump(r)
  995. regexp *r;
  996. {
  997.   register char *s;
  998.   register char op = EXACTLY;    /* Arbitrary non-END op. */
  999.   register char *next;
  1000.  
  1001.   s = r->program + 1;
  1002.   while (op != END) {        /* While that wasn't END last time... */
  1003.     op = OP(s);
  1004.     printf("%2d%s", (int) (s - r->program), regprop(s));    /* Where, what. */
  1005.     next = regnext(s);
  1006.     if (next == (char *)NULL)    /* Next ptr. */
  1007.         printf("(0)");
  1008.     else
  1009.         printf("(%d)", (int) (s - r->program) + (int) (next - s));
  1010.     s += 3;
  1011.     if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1012.         /* Literal string, where present. */
  1013.         while (*s != '\0') {
  1014.             putchar(*s);
  1015.             s++;
  1016.         }
  1017.         s++;
  1018.     }
  1019.     putchar('\n');
  1020.   }
  1021.  
  1022.   /* Header fields of interest. */
  1023.   if (r->regstart != '\0') printf("start `%c' ", r->regstart);
  1024.   if (r->reganch) printf("anchored ");
  1025.   if (r->regmust != (char *)NULL) printf("must have \"%s\"", r->regmust);
  1026.   printf("\n");
  1027. }
  1028.  
  1029. /*
  1030.  - regprop - printable representation of opcode
  1031.  */
  1032. static char *regprop(op)
  1033. char *op;
  1034. {
  1035.   register char *p;
  1036.   static char buf[50];
  1037.  
  1038.   (void) strcpy(buf, ":");
  1039.  
  1040.   switch (OP(op)) {
  1041.       case BOL:    p = "BOL";          break;
  1042.       case EOL:    p = "EOL";          break;
  1043.       case ANY:    p = "ANY";          break;
  1044.       case ANYOF:    p = "ANYOF";          break;
  1045.       case ANYBUT:    p = "ANYBUT";          break;
  1046.       case BRANCH:    p = "BRANCH";          break;
  1047.       case EXACTLY:    p = "EXACTLY";          break;
  1048.       case NOTHING:    p = "NOTHING";          break;
  1049.       case BACK:    p = "BACK";          break;
  1050.       case END:    p = "END";          break;
  1051.       case OPEN + 1:
  1052.       case OPEN + 2:
  1053.       case OPEN + 3:
  1054.       case OPEN + 4:
  1055.       case OPEN + 5:
  1056.       case OPEN + 6:
  1057.       case OPEN + 7:
  1058.       case OPEN + 8:
  1059.       case OPEN + 9:
  1060.     sprintf(buf + strlen(buf), "OPEN%d", OP(op) - OPEN);
  1061.     p = (char *)NULL;
  1062.     break;
  1063.       case CLOSE + 1:
  1064.       case CLOSE + 2:
  1065.       case CLOSE + 3:
  1066.       case CLOSE + 4:
  1067.       case CLOSE + 5:
  1068.       case CLOSE + 6:
  1069.       case CLOSE + 7:
  1070.       case CLOSE + 8:
  1071.       case CLOSE + 9:
  1072.     sprintf(buf + strlen(buf), "CLOSE%d", OP(op) - CLOSE);
  1073.     p = (char *)NULL;
  1074.     break;
  1075.       case STAR:    p = "STAR";          break;
  1076.       case PLUS:    p = "PLUS";          break;
  1077.       default:    regerror("corrupted opcode"); p = (char *) NULL; break;
  1078.   }
  1079.   if (p != (char *)NULL) (void) strcat(buf, p);
  1080.   return(buf);
  1081. }
  1082.  
  1083. #endif
  1084.